home *** CD-ROM | disk | FTP | other *** search
/ Cre@te Online 2000 December / Cre@teOnline CD05.iso / MacSoft / XML Instance.sea / XML Instance / Required / ccs_util.jar / regex / RegExpDFA.class (.txt) < prev    next >
Encoding:
Java Class File  |  1999-12-09  |  3.8 KB  |  174 lines
  1. package regex;
  2.  
  3. import java.util.BitSet;
  4. import java.util.Enumeration;
  5. import java.util.Hashtable;
  6.  
  7. class RegExpDFA {
  8.    private RegExpNFA nfa;
  9.    private Hashtable dfa = new Hashtable();
  10.    private DState initialDfaState;
  11.    private int count = 0;
  12.    private boolean hasLHead = false;
  13.    private boolean hasLTail = false;
  14.  
  15.    private void markEmptyTransition(BitSet var1, int var2) {
  16.       var1.set(var2);
  17.  
  18.       for(NList var3 = this.nfa.getNList(var2); var3 != null; var3 = var3.next()) {
  19.          if (var3.chars().isEmpty() && !var1.get(var3.to())) {
  20.             this.markEmptyTransition(var1, var3.to());
  21.          }
  22.       }
  23.  
  24.    }
  25.  
  26.    public DState nextState(DState var1, char var2) {
  27.       for(DSList var3 = var1.next(); var3 != null; var3 = var3.next()) {
  28.          if (var3.chars().has(var2)) {
  29.             return var3.to();
  30.          }
  31.       }
  32.  
  33.       return null;
  34.    }
  35.  
  36.    public DState nextState(DState var1, int var2) {
  37.       for(DSList var3 = var1.next(); var3 != null; var3 = var3.next()) {
  38.          if (var3.chars().type() == var2) {
  39.             return var3.to();
  40.          }
  41.       }
  42.  
  43.       return null;
  44.    }
  45.  
  46.    public DState getDState(int var1) {
  47.       Integer var2 = new Integer(var1);
  48.       return (DState)this.dfa.get(var2);
  49.    }
  50.  
  51.    public RegExpDFA(RegExpNFA var1) {
  52.       this.nfa = var1;
  53.       this.convertNfaToDfa();
  54.    }
  55.  
  56.    private DState fetchUnvisitedDState() {
  57.       Enumeration var1 = this.dfa.elements();
  58.  
  59.       while(var1.hasMoreElements()) {
  60.          DState var2 = (DState)var1.nextElement();
  61.          if (!var2.visited()) {
  62.             return var2;
  63.          }
  64.       }
  65.  
  66.       return null;
  67.    }
  68.  
  69.    private DList computeReachableNState(DState var1) {
  70.       boolean var8 = false;
  71.       BitSet var7 = var1.nfaStateSet();
  72.       DList var4 = null;
  73.  
  74.       for(int var2 = 0; var2 < this.nfa.count(); ++var2) {
  75.          if (var7.get(var2)) {
  76.             for(NList var3 = this.nfa.getNList(var2); var3 != null; var3 = var3.next()) {
  77.                if (!var3.chars().isEmpty()) {
  78.                   var8 = false;
  79.  
  80.                   for(DList var5 = var4; var5 != null; var5 = var5.next()) {
  81.                      if (var5.chars().equals(var3.chars())) {
  82.                         var5.to().set(var3.to());
  83.                         var8 = true;
  84.                         break;
  85.                      }
  86.                   }
  87.  
  88.                   if (!var8) {
  89.                      DList var6 = new DList(var3.chars(), new BitSet(), (DList)null);
  90.                      var6.to().set(var3.to());
  91.                      var6.setNext(var4);
  92.                      var4 = var6;
  93.                   }
  94.                }
  95.             }
  96.          }
  97.       }
  98.  
  99.       return var4;
  100.    }
  101.  
  102.    public DState initialState() {
  103.       return this.initialDfaState;
  104.    }
  105.  
  106.    private void collectEmptyTransition(BitSet var1) {
  107.       for(int var2 = 0; var2 < this.nfa.count(); ++var2) {
  108.          if (var1.get(var2)) {
  109.             this.markEmptyTransition(var1, var2);
  110.          }
  111.       }
  112.  
  113.    }
  114.  
  115.    public RTree getTree() {
  116.       return this.nfa.getTree();
  117.    }
  118.  
  119.    public RegExpNFA getNfa() {
  120.       return this.nfa;
  121.    }
  122.  
  123.    private DState registerDState(BitSet var1) {
  124.       Enumeration var2 = this.dfa.elements();
  125.  
  126.       while(var2.hasMoreElements()) {
  127.          DState var3 = (DState)var2.nextElement();
  128.          if (var3.nfaStateSet().equals(var1)) {
  129.             return var3;
  130.          }
  131.       }
  132.  
  133.       DState var4 = new DState(var1, false, var1.get(this.nfa.exit()), (DSList)null);
  134.       this.dfa.put(new Integer(this.count), var4);
  135.       ++this.count;
  136.       return var4;
  137.    }
  138.  
  139.    public boolean hasLHead() {
  140.       return this.hasLHead;
  141.    }
  142.  
  143.    public boolean hasLTail() {
  144.       return this.hasLTail;
  145.    }
  146.  
  147.    public int count() {
  148.       return this.count;
  149.    }
  150.  
  151.    private void convertNfaToDfa() {
  152.       BitSet var1 = new BitSet();
  153.       var1.set(this.nfa.entry());
  154.       this.collectEmptyTransition(var1);
  155.       this.initialDfaState = this.registerDState(var1);
  156.  
  157.       DState var2;
  158.       while((var2 = this.fetchUnvisitedDState()) != null) {
  159.          var2.visit();
  160.  
  161.          for(DList var3 = this.computeReachableNState(var2); var3 != null; var3 = var3.next()) {
  162.             this.collectEmptyTransition(var3.to());
  163.             DSList var4 = new DSList(var3.chars(), (DState)null, (DSList)null);
  164.             var4.setTo(this.registerDState(var3.to()));
  165.             var4.setNext(var2.next());
  166.             var2.setNext(var4);
  167.          }
  168.       }
  169.  
  170.       this.hasLHead = this.nfa.hasLHead();
  171.       this.hasLTail = this.nfa.hasLTail();
  172.    }
  173. }
  174.